/*
提交链接：https://leetcode.cn/problems/longest-consecutive-sequence/submissions/573453798
128. 最长连续序列-中等
完成日期：2024/10/17
并查集
*/

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_set<int> numSet(nums.begin(), nums.end()); // 将数组中的元素存入哈希集合
        int maxLength = 0; // 记录最长连续序列的长度
        for (int num : numSet) {
            // 如果 num - 1 不在集合中，说明 num 是一个序列的起始元素
            if (numSet.find(num - 1) == numSet.end()) {
                int currentNum = num;
                int currentLength = 1;
                // 检查 num + 1, num + 2, ... 是否在集合中
                while (numSet.find(currentNum + 1) != numSet.end()) {
                    currentNum++;
                    currentLength++;
                }
                // 更新最长长度
                maxLength = max(maxLength, currentLength);
            }
        }
        return maxLength; // 返回最长连续序列的长度
    }
};